/*
https://leetcode.cn/problems/accounts-merge/description/
721.账户合并
方钊堉 2024.10.13
并查集
*/

class Solution {
    vector<int> parents; // 存储每个节点的父节点

public:
    // 查找函数，带路径压缩优化
    int findRoot(int r) {
        if (r == parents[r]) {
            return r;
        }
        parents[r] = findRoot(parents[r]); // 路径压缩
        return parents[r];
    }

    // 合并两个节点所在的集合
    void merge(int i, int j) {
        int rootI = findRoot(i);
        int rootJ = findRoot(j);
        parents[rootI] = rootJ;
    }

    // 合并账户并返回结果
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, int> emailToAccount; // 存储每个邮箱对应的账户索引
        int accountSize = accounts.size();

        // 初始化并查集
        for (int i = 0; i < accountSize; ++i) {
            parents.push_back(i);
            int subSize = accounts[i].size();
            for (int j = 1; j < subSize; ++j) {
                if (emailToAccount.count(accounts[i][j])) {
                    merge(i, emailToAccount[accounts[i][j]]);
                }
                emailToAccount[accounts[i][j]] = i;
            }
        }

        // 构建每个根节点对应的账户列表
        unordered_map<int, vector<int>> rootToAccounts;
        for (int i = 0; i < accountSize; ++i) {
            rootToAccounts[findRoot(i)].push_back(i);
        }

        // 构建最终的结果
        vector<vector<string>> result;
        for (auto& [root, accountList] : rootToAccounts) {
            vector<string> mergedAccount;
            mergedAccount.push_back(accounts[root][0]); // 添加账户名称
            set<string> emails; // 使用集合去重
            for (int accountIndex : accountList) {
                int subSize = accounts[accountIndex].size();
                for (int j = 1; j < subSize; ++j) {
                    emails.insert(accounts[accountIndex][j]);
                }
            }
            for (const string& email : emails) {
                mergedAccount.push_back(email);
            }
            result.push_back(mergedAccount);
        }

        return result;
    }
};